# -*- coding=utf-8-*-
"""
@File:memory_selection
@Author:Created by Han X.Y
@Date:on 2021/7/12 16:03 
"""

"""
给定一个非负整数 numRows，生成杨辉三角的前 numRows 行。

输入: 5
输出:
[
     [1],
    [1,1],
   [1,2,1],
  [1,3,3,1],
 [1,4,6,4,1]
]

"""


class Solution:
    def generate(self, numRows):
        """
        杨辉三角形
        """
        # 最终输出
        final_res = []
        if numRows == 1:
            return [[1]]
        elif numRows == 2:
            return [[1], [1] * 2]
        else:
            for i in range(1, numRows + 1):
                if i <= 2:
                    final_res.append([1] * i)
                else:
                    tmp = []
                    for j in range(i - 1-1):#三角形是从1开始计数
                        # print(f'i-1={i-1},j={i},final_res[-1]={final_res[-1]}')
                        tmp.append(final_res[-1][j] + final_res[-1][j + 1])
                    final_res.append([1] + tmp + [1])
                # print(i, final_res)
            return final_res

if __name__=="__main__":
    s=Solution()
    print(s.generate(5))